package LeetCode.month01.day10;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class No84 {

    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new LinkedList<>();
        int[] right = new int[heights.length-1];
        int[] left = new int[heights.length-1];
        Arrays.fill(right,heights.length-1);
        for (int i = 0; i < heights.length; i++) {
            int height = heights[i];
            while(!stack.isEmpty()&&height<=heights[stack.peek()]){
                right[stack.pop()] = i;
            }
            left[i] = stack.isEmpty()?-1:stack.peek();
            stack.push(i);
        }
        int ans = 0;
        for (int i = 0; i < left.length; i++) {
            ans = Math.max(ans,(right[i]-left[i]-1)*heights[i]);
        }
        return ans;

        //暴力解法
//        int ans = 0;
//        for (int i = 0; i < heights.length; i++) {
//            int min = heights[i];
//            for (int j = i; j < heights.length; j++) {
//                if(heights[j]<min){
//                    min = heights[j];
//                }
//                ans = Math.max(ans,min*(j-i+1));
//            }
//        }
//        return ans;
    }
}
